package offer.day26;

import sun.reflect.generics.tree.Tree;

import java.util.Collections;
import java.util.Comparator;
import java.util.TreeSet;

public class No41GetMedian_RedBlackTree {
    /*
     * 面试题41：数据流中的中位数
     * 题目：如何得到一个数据流中的中位数？
     * 		如果从数据流中读出奇数个数值，那么中位数就是所有数值排序后位于中间的数值
     * 		如果从数据流中读出偶数个数值，那么重欸书九时左右数值排序后中间两个数的平均值
     *
     * 思路：其中数据流中的数据是不断变化的，需要在数据增加之后将其读取到容器中，
     * 其中容器可以使用数组，排序的链表，二叉搜索树，平衡的二叉搜索树（AVL树），最大堆+最小堆实现
     * 其中最大堆+最小堆  得到中位数的时间复杂度为O(1)  插入新的匀速的时间复杂度O(logn)
     *
     * 最大堆+最小堆实现过程：
     * 当数据的个数是奇数个时，中位数为p1，p2共同指向的数
     * 当数据的个数为偶数个时，中位数位p1，p2分别指向的两个数的平均值
     * 分析其过程发现容器中的数据被中位数分为两部分 ：左侧都比右侧小，p1指向的是左侧中最大的，p2指向的是右侧中最小的
     * 因而对两侧进行建堆，左侧为最大堆，右侧为最小堆，其中堆顶就是p1、p2指向的数
     *
     * 具体实现过程：
     * 1>首先要保证数据平均的分配到两个堆中，两个堆中的数目之差不能够超过1，
     * 		因此规定：当数据的总数目（两个堆数目之和）为偶数时，将新数据插入到最小堆；若为奇数，将新数据插入到最大堆
     * 2>还要保证最大堆中的数据都小于最小堆的数据：
     * 		当总数是偶数时，插入了最小堆，但是这个新的元素却比最大堆中的一些元素要小，应当是最大堆，
     * 		解决方法：在插入到最小堆之前，应当先将新元素插入到最大堆，然后把最大堆中的最大值取出插入到最小堆中，
     * 			   这样就能保证插入的值都是比最大堆数值大了
     * 		当总数为奇数时，插入到最大堆，但是这个新元素却比最小堆中的一些元素要大，应当插入最小堆，
     * 			   要上诉情况类似，不在赘述
     *
     * 可以使用优先队列、红黑树实现最大堆+最小堆
     * 本例使用优先队列实现
     * insert()方法读取数据流   GetMedian()方法获取数据流中的中位数
     * */
    TreeSet<Integer> minHeap=new TreeSet<>();
    TreeSet<Integer> maxHeap=new TreeSet<>(Collections.reverseOrder());
    public static void main(String[] args) {
        No41GetMedian_RedBlackTree g = new No41GetMedian_RedBlackTree();
        g.insert(1);
        g.insert(2);
        g.insert(3);
        g.insert(4);
        g.insert(5);
        System.out.println(g.getMedian());
    }

    private void insert(int num){
        if(((minHeap.size()+ maxHeap.size())&1)==1){
            minHeap.add(num);
            maxHeap.add(minHeap.pollFirst());
        }else{
            maxHeap.add(num);
            minHeap.add(maxHeap.pollFirst());
        }
    }

    private Double getMedian(){
        if(((minHeap.size()+ maxHeap.size())&1)==0) return null;
        if(((minHeap.size()+ maxHeap.size())&1)==1){
            return Double.valueOf(minHeap.pollFirst());
        }else{
            return Double.valueOf((maxHeap.pollFirst()+minHeap.pollFirst())/2);
        }
    }
}
